package org.regotto.basics.find;

import org.regotto.common.Data;

/**
 * 有序列表找出相同数最开始出现的位置以及最后出现的位置
 */
public class BinarySearch {

    public static void main(String[] args) {
        binarySearchFirAndLas(3, Data.getInts(true));
    }

    public static void binarySearchFirAndLas(int x, int q[]) {
        int l = 0, r = q.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (q[mid] < x) l = mid + 1;
            else r = mid;
        }
        if (q[l] != x) System.out.println("不存在");
        else {
            System.out.print(l + " ");
            l = 0; r = q.length - 1;
            while (l < r) {
                int mid = (l + r) / 2 + 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            System.out.println(r);
        }
    }

}
